package basic.courseLearn08.problem;


import org.junit.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

//项目宣讲问题，一个会议室，有多个项目需要宣讲，每个项目都有不同的时间，需要安排好时间，如何安排能够使得尽可能多的项目都能宣讲完？
public class ItemManage {

    //项目安排--贪心策略：以结束时间早作为贪心策略
    public Integer manage(Program[] programs){
        //1. 定义小根堆，按照结束时间排序；定义num数目
        int num=0,startTime=0;
        PriorityQueue<Program> minHeap = new PriorityQueue<>(new MinComparator());
        //2. 所有项目加入堆
        for (Program program : programs) {
            minHeap.add(program);
        }
        //3. 循环，直到堆为空
        while (!minHeap.isEmpty()){
            //3.1 取出堆顶项目
            Program program = minHeap.poll();
            //3.2 判断开始时间是否满足条件
            if (program.startTime>=startTime){
                num++;
                startTime=program.endTime;
            }

        }
        return num;
    }

    public class MinComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o1.endTime-o2.endTime;
        }
    }

    //项目开始结束时间
    public class Program{
        public int startTime;
        public int endTime;
        public Program(int startTime, int endTime){
            this.startTime = startTime;
            this.endTime = endTime;
        }
    }

    @Test
    public void test(){
        Program program1 = new Program(8, 9);
        Program program2 = new Program(10, 14);
        Program program3 = new Program(9, 11);
        Program program4 = new Program(12, 13);
        Program program5 = new Program(14, 18);
        Program program6 = new Program(15, 16);

        Program[] programs = {program1, program2, program3, program4, program5, program6};
        System.out.println("最多宣讲项目数：" + manage(programs));

    }

}
